//两个链表的第一个公共结点: https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
  public:
    ListNode* GetListLength(ListNode* list, int& len) { //len 是一个输出型参数
        if (list == nullptr) 
		{
            return list;
        }
        ListNode* end = list;
        while (list) 
		{
            end = list;
            list = list->next;
            len++;
        }
        return end;
    }

	//根据上面的题面，可以看出，是单链表
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr || pHead2 == nullptr) 
		{
            return nullptr;
        }
        int length1 = 0;
        int length2 = 0;
        ListNode* end1 = GetListLength(pHead1, length1);
        ListNode* end2 = GetListLength(pHead2, length2);
        if (end1 != end2) 
		{
			//说明两张链表根本就没有公共节点，其实这里不用判定也行，但是提前判定，后续就不用在忙活了
			//当然，你如果不想这样写，也可以，参加后面的java代码
            return nullptr;
        }
        int step = abs(length1 - length2);
        if (length1 > length2) 
		{
            while (step) 
			{
                pHead1 = pHead1->next;
                step--;
            }
        } 
		else
		{
            while (step) 
			{
                pHead2 = pHead2->next;
                step--;
            }
        }
        while (pHead1 && pHead2) 
		{
            if (pHead1 == pHead2) 
			{
                return pHead1;
            }
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return nullptr;
    }
};